package offer2

/**
重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

思路：
前序遍历: 根、左、右
中序遍历：左、根、右

通过上述观察，我们可以发现
1.前序遍历序列的第一个元素是根
2.在中序遍历序列中，根的两边分别是左子树和右子树的中序序列

获取前序遍历的首位元素,该位置是根元素
查找中序遍历数组，根元素所在的位置，
从[0,根元素index-1]为左子树的中序遍历序列
从[根元素index+1, len(arr)-1]为右子树的中序遍历序列

通过中序序列的根的两边的左右子树的各自的长度，可以将前序序列除根以外的后面所有元素划分为：
两个前序序列的左、右子树序列。 这两个前序的左、右子树序列同样遵循上述三点规律
在重建二叉树时，我们可以自底向上递归地构建二叉树

三个函数实现上述三个功能
1.take函数：执行第一步，取出根元素，并返回剩下元素组成的切片
2.div_mid函数：执行第二步，将中序遍历序列按根的两边划分为左子树和右子树
3.div_two函数：执行第三步，按左右子树的各自的长度可以将前序序列除根以外的后面所有元素划分为
两个前序的左、右子树序列。

然后用 fen函数将上述三个步骤组合起来。
最后在总函数 buildTree中实现递归调用。

go语言代码:

*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 && len(inorder) == 0 {
		return nil
	}

	// 取 preorder 的第一个值 value，并将 preorder 分成左子树 p1 和右子树 p2 ，
	//将 inorder 分成左子树 i1 和右子树 i2
	value, i1, i2, p1, p2 := fen(preorder, inorder)
	// 新建节点
	newpoint := &TreeNode{Val: value}
	// 递归调用
	newpoint.Left = buildTree(p1, i1)
	newpoint.Right = buildTree(p2, i2)
	return newpoint

}

// 将 preorder 分成左子树p1和右子树p2，将 inorder 分成左子树i1和右子树i2
func fen(preorder []int, inorder []int) (int, []int, []int, []int, []int) {
	value, preorder := take(preorder)
	i1, i2 := div_mid(value, inorder)
	p1, p2 := div_two(len(i1), preorder)
	return value, i1, i2, p1, p2
}

func take(intput []int) (a int, output []int) {
	if len(intput) > 0 {
		output = intput[1:]
		return intput[0], output
	} else {
		return 0, intput
	}
}

// 将切片以值 a 为分界线，划分为左右两部分
func div_mid(a int, input []int) (div1 []int, div2 []int) {

	//如果len(input) > 0,遍历input, 以该值作为分割点, 分为左右两个中序序列
	if len(input) > 0 {
		for i, j := range input {
			if j == a {
				div1 := input[:i]
				div2 := input[i+1:]
				return div1, div2
			}
		}
	} else {
		return nil, nil
	}

	return nil, nil
}

// 将切片划分为两部分，第一部分长度为 len1，剩下的为第二部分
func div_two(len1 int, intput []int) (div1 []int, div2 []int) {
	if len1 < len(intput) {
		div1 := intput[:len1]
		div2 := intput[len1:]
		return div1, div2
	} else if len1 == len(intput) {
		return intput, []int{}
	} else {
		return nil, nil
	}
}
